//
// Created by hay boy on 2022/7/13.
//

#ifndef ALGORITHMS_HASH_H
#define ALGORITHMS_HASH_H
#include <string>
#include <unordered_map>
#include "hashTableFull.h"
#include "../dictionary/dictionary.h"
#include "../dictionary/SortedChain.h"
using namespace std;

class Hash{
public:
    size_t operator()(const string theKey)const{
        unsigned long hashValue = 0;
        int length = (int)theKey.length();
        for(int i = 0;i<length;i++){
            hashValue = hashValue*5+theKey.at(i);
        }
        return size_t(hashValue);
    }
};

template<class K,class E>
class HashTable{
protected:
    pair<const K,E>** table;
    hash<K> hash;
    int dSize;
    int divisor;
    explicit HashTable(int divisor){
        this->divisor = divisor;
        dSize = 0;
        table = new pair<const K,E>*[divisor];
        for(int i = 0;i<divisor;i++){
            table[i] = nullptr;
        }
    }
    int search(const K& theKey)const{
        int i = (int)hash(theKey)%divisor;
        int j = i;
        do{
            if(table[j]==nullptr||table[j]->first==theKey){
                return j;
            }
            j = (j+1)%divisor;
        }while(j!=i);
        return j;
    }
    pair<const K,E>* find(const K& theKey)const{
        int b = search(theKey);
        if(table[b] == nullptr||table[b]->first!=theKey){
            return nullptr;
        }
        return table[b];
    }
    void insert(const pair<const K,E>& thePair){
        int b = search(thePair.first);
        if(table[b]== nullptr) {
            table[b] = new pair<const K, E>(thePair);
            dSize++;
        }else{
            if(table[b]->first==thePair.first){
                table[b]->second = thePair.second;
            }else{
                throw hashTableFull();
            }
        }
    }
};
template<class K,class E>
class HashChains:public Dictionary<K,E>{
protected:
    int divisor{};
    int dSize;
    hash<K> hash;
    SortedChain<K,E>* table;
public:
    explicit HashChains(int divisor=11){
        this->divisor = divisor;
        dSize = 0;
        table = new SortedChain<K,E>[divisor];
    }
    ~HashChains(){
        delete []table;
    }
    bool empty()const{
        return dSize==0;
    }
    int size()const{
        return dSize;
    }

    pair<const K,E>*  find(const K& theKey)const{
        return table[hash(theKey)%divisor].find(theKey);
    }
    void insert(const pair<const K,E>& thePair){
        int homeBucket = (int)hash(thePair.first)%divisor;
        int homeSize = table[homeBucket].size();
        table[homeBucket].insert(thePair);
        if(table[homeBucket].size()>homeSize){
            dSize++;
        }
    }
    void clear(){
        for(int i = 0;i<divisor;i++){
            table[i].~SortedChain();
        }
        dSize = 0;
    }
    void erase(const K& theKey){
        table[hash(theKey)%divisor].erase(theKey);
    }
    void output(ostream& out)const{
        for(int i = 0;i<divisor;i++){
            if(table[i].size()==0){
                cout<<"null"<<endl;
            }else{
                cout<<table[i]<<endl;
            }
        }
    }
    template<class F,class G>
    friend ostream& operator<<(ostream& out,const HashChains<F,G>& x){
        x.output(out);
        return out;
    }

};
#endif //ALGORITHMS_HASH_H
